#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 240. 搜索二维矩阵 II.py
@time: 2022/1/29 17:20
@desc: https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
> 编写一个高效的算法来搜索mxn矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
    - 每行的元素从左到右升序排列。
    - 每列的元素从上到下升序排列。

@解题思路：
    1. 压缩搜索区域
    2. Ot(m+n), Os(1)
'''

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        m, n = len(matrix), len(matrix[0])
        x, y = 0, n-1
        while x<m and y>=0:
            if matrix[x][y]==target: return True
            elif matrix[x][y]>target:
                # 当前列所有元素都比target大，可以排除，向左压缩
                y -= 1
            else:
                # 当前行所有元素都比target小，可以排除，向下压缩
                x += 1
        return False